package com.zlsy.learning.leetcode.stack.s155;

/**
 * @author zhouliang
 * @date 2020/8/11 13:56 方法二、使用链表
 *     <p>时间复杂度：O（1） 空间复杂度：O（N）
 */
public class MinStack3 {

  private Node head;

  public MinStack3() {}

  public void push(int x) {
    if (head == null) {
      head = new Node(x, x);
    } else {
      // 1、把放入链表头部，2、设置val和min（当前值和head的min比较【必须保证head的min就是最小的】取最小 3、当前.next = 之前的值）
      head = new Node(x, Math.min(x, head.min), head);
    }
  }

  /** 移除栈顶元素 （为什么为void的原因：因为head=head.next就是移除头结点） */
  public void pop() {
    head = head.next;
  }

  public int top() {
    return head.val;
  }

  public int getMin() {
    return head.min;
  }

  private static class Node {
    int val;
    int min;
    Node next;

    public Node(int val, int min) {
      this(val, min, null);
    }

    public Node(int val, int min, Node next) {
      this.val = val;
      this.min = min;
      this.next = next;
    }
  }
}
